package hot_100;

import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class 电话号码的字母组合 {
    public static void main(String[] args) {

    }

    char[] array;
    int n;
    List<String> ans = new LinkedList<>();

    public List<String> letterCombinations(String digits) {
        array = digits.toCharArray();
        n = digits.length();
        Dfs(0, "");
        return ans;
    }

    public void Dfs(int x, String s) {
        if (x == n) {
            if (!Objects.equals(s, ""))
                ans.add(s);
            return;
        }
        int num = array[x] - '2';
        char c = (char) ('a' + num * 3);
        for (char i = c; i < (char) (c + 3); i++) {
            if (num <= 5)
                Dfs(x + 1, s + i);
            else
                Dfs(x + 1, s + (char) (i + 1));
        }
        if (num == 5) {
            Dfs(x + 1, s + 's');
        }

        if (num == 7)
            Dfs(x + 1, s + 'z');
    }
}
